//https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/?envType=daily-question&envId=2024-03-14


class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        //动态规划，从后向前走
        //dp[i] = nums[i]>=nums[i-1]?dp[i+1]+nums[i]:nums[i];
        int n = nums.size();
        vector<long long> dp(n);
        dp[n-1] = nums[n-1];
        long long ans = (long long)nums[n-1];
        for(int i = n-2;i>=0;--i)
        {
            dp[i] = dp[i+1]>=nums[i]?dp[i+1]+(long long)nums[i]:(long long)nums[i];
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};